import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-05-26
 * Time: 23:11
 */
public class Solution {
    // 利用拓扑排序
    // 哪个节点的入度为 0 选择哪个节点
    // 将每个序列都按照一个有向图进行连接
    // 进行拓扑排序时, 如果同时出现了两个节点的入度为 0 说明最短序列不唯一
    // 这里基本上没有用到过nums数组
    public boolean sequenceReconstruction(int[] nums, int[][] sequences) {
        int n = nums.length;
        // 记录每个节点的入度, 下标表示 节点号
        int[] inDegrees = new int[n + 1];
        // 记录每个节点对应的邻接点, 同样下标表示节点号
        // 使用 set 不是为了存取快, 而是为了去重
        // 因为 sequences 数组并不是给定了某个节点的邻接矩阵
        // 所以我们需要先记录每个几点都连接了哪几个节点
        // 但是这个记录的过程中, 可能会重复, 所以用 set
        Set<Integer>[] nodes = new Set[n + 1];
        for (int i = 0; i <= n; i++) {
            nodes[i] = new HashSet<>();
        }
        for (int[] sequence: sequences) {
            int size = sequence.length;
            for (int i = 1; i < size; i++) {
                // 源节点
                int from = sequence[i-1];
                // 目的节点
                int to = sequence[i];
                // 添加成功了再 入度+1, 因为可能重复记录
                if (nodes[from].add(to)){
                    inDegrees[to]++;
                }
            }
        }

        Queue<Integer> queue = new LinkedList<>();
        // 将入度为 0 的节点放到队列中
        for (int i = 1; i <= n; i++) {
            if (inDegrees[i] == 0){
                queue.add(i);
            }
        }

        while (!queue.isEmpty()){
            // 如果队列中 入度为0 的节点不只一个, 那么说明最短队列不唯一
            if (queue.size() > 1){
                return false;
            }
            int value = queue.poll();
            // 将这个节点以及对应的边删除, 以便找到下一个入度为 0 的节点
            Set<Integer> set = nodes[value];
            for (int next: set) {
                inDegrees[next]--;
                if (inDegrees[next] == 0){
                    queue.add(next);
                }
            }
        }
        return true;
    }
}
